﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
/// <summary>
/// 层序遍历 广度优先搜索
/// </summary>
namespace BinarTtree.LevelOrder
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class MainProject
    {
       
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            //TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
            TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));

            LevelOrder(treeNode);
            Console.ReadKey();
        }
        public static IList<IList<int>> LevelOrder(TreeNode root)
        {
            IList<IList<int>> levelList = new List<IList<int>>();
            Level(root, levelList);
            return levelList;
        }

        public static void Level(TreeNode treeNode, IList<IList<int>> rootList)
        {
            if (treeNode==null)
            {
                return;
            }
            Queue<TreeNode> treeNodes = new Queue<TreeNode>();
            treeNodes.Enqueue(treeNode);
            while (treeNodes.Count>0)
            {
                int size = treeNodes.Count;
                List<int> list = new List<int>();
                for (int i = 0; i < size; i++)
                {
                    TreeNode treeNode1 = treeNodes.Dequeue();
                    if (treeNode1.left!=null)
                    {
                        treeNodes.Enqueue(treeNode1.left);
                    }
                    if (treeNode1.right != null)
                    {
                        treeNodes.Enqueue(treeNode1.right);
                    }
                    list.Add(treeNode1.val);
                }
                rootList.Add(list);
            }
        }
    }
}
